package datastructure;

/**
 * @Author leecho
 * @Date: 2021/10/10 12:00
 * @Version 1.0
 */

public class SingleLinkListDemo {
    public static void main(String[] args) {
        SingleLinkList singleLinkList = new SingleLinkList();
        singleLinkList.addByNo(new HeroNode(1,"宋江","及时雨"));
        singleLinkList.addByNo(new HeroNode(2,"卢俊义","玉麒麟"));
        singleLinkList.addByNo(new HeroNode(3,"吴用","智多星"));
        singleLinkList.addByNo(new HeroNode(5,"林冲","包子头"));
        singleLinkList.addByNo(new HeroNode(4,"林冲","包子头"));

        singleLinkList.list();

        System.out.println("反转");
        singleLinkList.reverseLink(singleLinkList.getHead());
        singleLinkList.list();
    }

}


class SingleLinkList{
    // 初始化一个头结点，在这个单链表中头结点为空没有数据，作用为找到该链表
    private HeroNode head = new HeroNode(0,"","");

    public HeroNode getHead() {
        return head;
    }

    // 添加一个节点
    public void add(HeroNode heroNode){
        // 因为头结点不能改变，所以定义一个临时节点来指向每一个节点
        HeroNode temp = head;

        while (true) {
            if (temp.next == null){
                break;
            }
            temp = temp.next;
        }
        temp.next = heroNode;
    }



    public void reverseLink(HeroNode head){
        /*
        * 思路：
        * - 创建一个临时节点将头结点赋值给它，找到链表
        * - 创建一个新的头结点，依次取下原链表的节点，将取下的节点挂在新节点的后面
        *   - 临时节点遍历每一个节点，当遍历到的时候，将新节点的next赋值给它，这样它就挂在了新头节点的后面
        * - 最后遍历完以后，将新头结点的next赋值给原头结点，这样则实现了链表的反转
        * */
        HeroNode temp = head.next;
        HeroNode next = null;
        HeroNode n1 = new HeroNode(0,"","");

        while (temp != null){
            next = temp.next;
            temp.next = n1.next;
            n1.next = temp;
            temp = next;
        }
        head.next = n1.next;
    }

    // 通过编号添加节点
    public void addByNo(HeroNode heroNode){
        /*
        * 思路
        * - 设置临时节点来遍历所有节点，遍历到每一个节点以后，判断当前遍历到的节点的下一个节点的值和添加的值
        *   - 大于则找到，添加到当前遍历节点的下一个
        *   - 现在存在的链表中有等于的值，则无法添加
        *   - 如果一直遍历，在链表现有的值中没有比其大的，则直接添加到最后一个
        * */
        HeroNode temp = head;
        boolean flag = false;
        while (true){
            if (temp.next == null)
                break;
            if (temp.next.getNo() > heroNode.getNo()){
                break;
            } else if (temp.next.getNo() == heroNode.getNo()){
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if (!flag){
            heroNode.next = temp.next;
            temp.next = heroNode;
        } else {
            System.out.println("无法加入该编号的节点");
        }
    }

    // 遍历链表
    public void list(){
        if (head.next != null) {
            HeroNode temp = head;
            while (true) {
                temp = temp.next;
                System.out.println(temp);
                if (temp.next == null)
                    break;
            }
        } else {
            System.out.println("该链表为空");
            return;
        }
    }

}

class HeroNode{
    // 数据域
    private int no;
    private String name;
    private String nickname;
    // 指向下一个节点
    public HeroNode next;

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getNickname() {
        return nickname;
    }

    public void setNickname(String nickname) {
        this.nickname = nickname;
    }

    // 初始化一个节点，设置属性但初始化时其指向为空
    public HeroNode(int no, String name, String nickname){
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "datastructure.HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}